/*
 ------------------------------------------------------------------------------
 Copyright (C) 2006-2007 Team Blur.

 This file is part of the Quantum Engine source code.

 The Quantum Engine source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The Quantum Engine source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the Quantum Engine source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


#include "sg_local.h"


static clipSector_t *		sg_clipSectors;
static int					sg_numClipSectors;


/*
 ==============================================================================

 CLIP SECTORS

 ==============================================================================
*/


/*
 ==================
 SG_CreateClipSector

 Builds a uniformly divided tree for the given world size
 ==================
*/
static clipSector_t *SG_CreateClipSector (const odBounds &bounds, int depth){

	clipSector_t	*sector;
	odBounds		bounds1, bounds2;
	odVec3			size;

	sector = &sg_clipSectors[sg_numClipSectors++];

	if (depth == MAX_SECTOR_DEPTH){
		sector->axis = -1;
		sector->dist = 0.0f;

		sector->children[0] = NULL;
		sector->children[1] = NULL;

		sector->entities = NULL;

		return sector;
	}

	size = bounds[1] - bounds[0];

	if (size[0] > size[1])
		sector->axis = 0;
	else
		sector->axis = 1;

	sector->dist = (bounds[1][sector->axis] + bounds[0][sector->axis]) * 0.5f;

	bounds1 = bounds;
	bounds2 = bounds;

	bounds1[1][sector->axis] = bounds2[0][sector->axis] = sector->dist;

	sector->children[0] = SG_CreateClipSector(bounds2, depth+1);
	sector->children[1] = SG_CreateClipSector(bounds1, depth+1);

	sector->entities = NULL;

	return sector;
}

/*
 ==================
 SG_ListClipSectors_f
 ==================
*/
static void SG_ListClipSectors_f (void){

	clipSector_t	*sector;
	entity_t		*entity;
	int				i, count;

	for (i = 0, sector = sg_clipSectors; i < sg_numClipSectors; i++, sector++){
		count = 0;

		for (entity = sector->entities; entity; entity = entity->nextInClipSector)
			count++;

		odSystem->Printf("Sector %i: %i entities\n", i, count);
	}
}

/*
 ==================
 SG_InitClipSectors
 ==================
*/
void SG_InitClipSectors (void){

	clipModel_t	*clipModel;
	odBounds	bounds;
	odVec3		size;

	// Register our commands
	odCmdSystem->AddCommand("listClipSectors", SG_ListClipSectors_f, "Lists clip sectors");

	// Get clip map bounds
	clipModel = odCollision->RegisterModel("*0");

	odCollision->GetModelBounds(clipModel, bounds);

	size = bounds[1] - bounds[0];

	odSystem->Printf("Map size: %i x %i x %i\n", M_Ftol(size.x), M_Ftol(size.y), M_Ftol(size.z));

	// Allocate and create the clip sectors
	sg_clipSectors = (clipSector_t *)odMemory->Alloc(MAX_SECTORS * sizeof(clipSector_t), TAG_SERVER);

	SG_CreateClipSector(bounds, 0);
}

/*
 ==================
 SG_ShutdownClipSectors
 ==================
*/
void SG_ShutdownClipSectors (void){

	// Unregister our commands
	odCmdSystem->RemoveCommand("listClipSectors");

	// Free the clip sectors
	if (sg_clipSectors)
		odMemory->Free(sg_clipSectors);

	sg_clipSectors = NULL;
	sg_numClipSectors = 0;
}


/*
 ==============================================================================

 ENTITY LINKING AND CLIPPING

 ==============================================================================
*/

typedef struct entityList_s {
	odBounds				bounds;
	int						contentMask;

	const entity_t *		passEntity;
	const entity_t *		passOwner;

	entity_t **				entities;
	int						numEntities;
	int						maxEntities;
} entityList_t;


/*
 ==================
 SG_LinkEntity
 ==================
*/
void SG_LinkEntity (entity_t *entity){

	clipSector_t	*sector;
	int				areas[10];//BSP_MAX_AREAS];
	int				count;
	int				x, y, z;

	if (entity->clipSector)
		SG_UnlinkEntity(entity);	// Unlink from old position

	// Encode the bounding box size if needed
	if (!entity->clipModel){
		if (entity->contents){
			// Assume X and Y are symmetric
			x = M_FtolFast(entity->bounds[1][0]);
			y = M_FtolFast(entity->bounds[1][1]);

			// Assume Z mins is 0 and Z maxs is positive (the origin is at the
			// bottom-center)
			z = M_FtolFast(entity->bounds[1][2]);

			// Clamp and encode
			x = M_ClampLong(x, 1, 255);
			y = M_ClampLong(y, 1, 255);
			z = M_ClampLong(z, 1, 255);

			entity->state.solidBox = (z << 16) | (y << 8) | x;
			entity->state.solidContents = entity->contents;
		}
		else {
			// No collision at all
			entity->state.solidBox = 0;
			entity->state.solidContents = 0;
		}
	}

	// Compute the absolute bounds
	if (entity->angles.IsCleared())
		entity->absBounds = entity->bounds + entity->origin;
	else
		entity->absBounds.FromSphere(entity->origin, entity->bounds.GetRadius());

	// Because movement is clipped an epsilon away from an actual edge, we must
	// fully check even when bounding boxes don't quite touch
	entity->absBounds.Expand(CM_BOX_EPSILON);

	// If the entity is completely outside the world, it can be considered
	// unlinked
//	count = odCollision->BoundsInAreas(entity->absBounds, areas, BSP_MAX_AREAS);

	if (count == 1 && areas[0] == -1)
		return;

	// Find the first clip sector that the entity's bounding box crosses
	sector = sg_clipSectors;

	while (1){
		if (sector->axis == -1)
			break;

		if (entity->absBounds[0][sector->axis] > sector->dist)
			sector = sector->children[0];
		else if (entity->absBounds[1][sector->axis] < sector->dist)
			sector = sector->children[1];
		else
			break;		// Crosses the sector
	}

	// Link it in
	entity->clipSector = sector;
	entity->nextInClipSector = sector->entities;

	sector->entities = entity;

	entity->linked = true;
}

/*
 ==================
 SG_UnlinkEntity
 ==================
*/
void SG_UnlinkEntity (entity_t *entity){

	clipSector_t	*sector;
	entity_t		*scan;

	entity->linked = false;

	sector = entity->clipSector;
	if (!sector)
		return;		// Not linked in anywhere

	entity->clipSector = NULL;

	if (sector->entities == entity){
		sector->entities = entity->nextInClipSector;
		return;
	}

	for (scan = sector->entities; scan; scan = scan->nextInClipSector){
		if (scan->nextInClipSector == entity){
			scan->nextInClipSector = entity->nextInClipSector;
			return;
		}
	}

	odSystem->Printf(S_COLOR_YELLOW "SG_UnlinkEntity: entity %i not found in clipSectors\n", entity->state.number);
}

/*
 ==================
 SG_RecursiveEntitiesInBounds
 ==================
*/
static void SG_RecursiveEntitiesInBounds (clipSector_t *sector, entityList_t *entityList){

	entity_t	*entity;

	for (entity = sector->entities; entity; entity = entity->nextInClipSector){
		if (entity == entityList->passEntity)
			continue;		// Don't clip against the pass entity
		else if (entity == entityList->passOwner)
			continue;		// Don't clip against the pass owner
		else if (entity->owner){
			if (entity->owner == entityList->passEntity)
				continue;		// Don't clip against own missiles
			else if (entity->owner == entityList->passOwner)
				continue;		// Don't clip against other missiles from this owner
		}

		if (!entity->clipModel && !entity->state.solidBox)
			continue;		// Don't clip against this entity

		if (!(entity->contents & entityList->contentMask))
			continue;		// Doesn't have the contents we're looking for

		if (!entity->absBounds.IntersectsBounds(entityList->bounds))
			continue;		// Doesn't intersect the clip bounds

		// Add it to the entity list
		if (entityList->numEntities == entityList->maxEntities){
			odSystem->Printf(S_COLOR_YELLOW "SG_EntitiesInBounds: maxEntities hit\n");
			return;
		}

		entityList->entities[entityList->numEntities++] = entity;
	}

	if (sector->axis == -1)
		return;		// Terminal sector

	// Recurse down both sides
	if (entityList->bounds[1][sector->axis] > sector->dist)
		SG_RecursiveEntitiesInBounds(sector->children[0], entityList);
	if (entityList->bounds[0][sector->axis] < sector->dist)
		SG_RecursiveEntitiesInBounds(sector->children[1], entityList);
}

/*
 ==================
 SG_EntitiesInBounds
 ==================
*/
static int SG_EntitiesInBounds (const odBounds &bounds, int contentMask, int passEntityNum, entity_t **entities, int maxEntities){

	entity_t		*passEntity = NULL;
	entityList_t	entityList;

	if (passEntityNum >= 0 && passEntityNum < ENTITYNUM_MAX_NORMAL)
		passEntity = level.entities[passEntityNum];
	else if (passEntityNum == ENTITYNUM_WORLD)
		passEntity = level.entities[ENTITYNUM_WORLD];

	entityList.bounds = bounds;
	entityList.contentMask = contentMask;
	entityList.passEntity = passEntity;
	entityList.passOwner = (passEntity) ? passEntity->owner : NULL;
	entityList.entities = entities;
	entityList.numEntities = 0;
	entityList.maxEntities = maxEntities;

	SG_RecursiveEntitiesInBounds(sg_clipSectors, &entityList);

	return entityList.numEntities;
}

/*
 ==================
 SG_Contents
 ==================
*/
int SG_Contents (const odVec3 &point, const odBounds &bounds, int contentMask, int passEntityNum){

	entity_t	*entity, *entities[MAX_ENTITIES];
	clipModel_t	*clipModel;
	odBounds	contentsBounds;
	int			contents;
	int			i, count;

	// Test against the world
	if (passEntityNum != ENTITYNUM_WORLD)
		contents = odCollision->Contents(point, bounds, contentMask, NULL, vec3_origin, mat3_identity);
	else
		contents = 0;

	// Compute the contents bounds
	contentsBounds = bounds + point;
	contentsBounds.Expand(CM_BOX_EPSILON);

	// Test against the entities
	count = SG_EntitiesInBounds(contentsBounds, contentMask, passEntityNum, entities, MAX_ENTITIES);

	for (i = 0; i < count; i++){
		entity = entities[i];

		// TODO: don't test against dynamic models

		if ((entity->contents & contents) == entity->contents)
			continue;		// Doesn't have any new contents

		// Set up the clip model
		if (entity->clipModel)
			clipModel = entity->clipModel;
		else
			clipModel = odCollision->SetupBoxModel(entity->bounds, 0, entity->contents);

		// Test against the clip model
		contents |= odCollision->Contents(point, bounds, contentMask, clipModel, entity->origin, entity->axis);
	}

	return contents;
}

/*
 ==================
 SG_Trace
 ==================
*/
trace_t SG_Trace (const odVec3 &start, const odVec3 &end, const odBounds &bounds, int contentMask, int passEntityNum){

	entity_t	*entity, *entities[MAX_ENTITIES];
	clipModel_t	*clipModel;
	odBounds	traceBounds;
	odBounds	modelBounds;
	float		radius;
	trace_t		trace, tmp;
	int			i, j, count;

	// Trace through the world
	if (passEntityNum != ENTITYNUM_WORLD){
		trace = odCollision->Trace(start, end, bounds, contentMask, NULL, vec3_origin, mat3_identity);

		if (trace.fraction < 1.0f){
			trace.c.entityNum = ENTITYNUM_WORLD;

			if (trace.fraction == 0.0f)
				return trace;	// Blocked immediately by the world
		}
		else
			trace.c.entityNum = ENTITYNUM_NONE;
	}
	else {
		memset(&trace, 0, sizeof(trace_t));

		trace.fraction = 1.0f;
		trace.endPos = end;
		trace.c.entityNum = ENTITYNUM_NONE;
	}

	// Compute the trace bounds
	for (i = 0; i < 3; i++){
		if (trace.endPos[i] > start[i]){
			traceBounds[0][i] = start[i] + bounds[0][i] - CM_BOX_EPSILON;
			traceBounds[1][i] = trace.endPos[i] + bounds[1][i] + CM_BOX_EPSILON;
		}
		else {
			traceBounds[0][i] = trace.endPos[i] + bounds[0][i] - CM_BOX_EPSILON;
			traceBounds[1][i] = start[i] + bounds[1][i] + CM_BOX_EPSILON;
		}
	}

	radius = bounds.GetRadius();

	// Trace through the entities
	count = SG_EntitiesInBounds(traceBounds, contentMask, passEntityNum, entities, MAX_ENTITIES);

	for (i = 0; i < count; i++){
		entity = entities[i];

		if (!entity->absBounds.IntersectsBounds(traceBounds))
			continue;		// Doesn't intersect the clip bounds

		// Set up the clip model
		if (entity->clipModel){
			// TODO!!!

			// Check whether it is a static or a dynamic model
			if (0){
				// Yet another intersection test to try and reject traces
				// against dynamic models
				modelBounds = entity->absBounds;
				modelBounds.Expand(radius);

				if (!modelBounds.IntersectsLine(start, trace.endPos))
					continue;

				// TODO: animate the joints

				// Instantiate
				clipModel = odCollision->InstantiateDynamicModel(entity->clipModel, entity->state.number, NULL);
			}
			else
				clipModel = entity->clipModel;
		}
		else
			clipModel = odCollision->SetupBoxModel(entity->bounds, 0, entity->contents);

		// Trace through the clip model
		tmp = odCollision->Trace(start, end, bounds, contentMask, clipModel, entity->origin, entity->axis);

		if (tmp.fraction < trace.fraction){
			// Keep startInside from a previous trace
			if (trace.startInside)
				tmp.startInside = true;

			trace = tmp;
			trace.c.entityNum = entity->state.number;

			if (!trace.fraction)
				break;		// Blocked immediately by this entity

			// Recompute the trace bounds
			for (j = 0; j < 3; j++){
				if (trace.endPos[j] > start[j]){
					traceBounds[0][j] = start[j] + bounds[0][j] - CM_BOX_EPSILON;
					traceBounds[1][j] = trace.endPos[j] + bounds[1][j] + CM_BOX_EPSILON;
				}
				else {
					traceBounds[0][j] = trace.endPos[j] + bounds[0][j] - CM_BOX_EPSILON;
					traceBounds[1][j] = start[j] + bounds[1][j] + CM_BOX_EPSILON;
				}
			}
		}
		else if (tmp.startInside)
			trace.startInside = true;
	}

	return trace;
}
